The protection of sensitive information may be relevant to a wide variety of computing platforms ranging from personal computers (PCs) to servers. For example, without protection, an attacker with physical access to a platform may capture snapshots of encrypted sensitive data (e.g., banking login information) and replay the snapshots later in order to masquerade as a bona fide possessor of the sensitive data (e.g., in a “replay attack”). One approach to protecting against replay attacks may be to use counter mode encryption and a counter tree structure. With counter mode encryption, accessing sensitive data may be decoupled from the cryptographic work that encrypts the data (e.g., stored in cache lines). Instead of the sensitive data, a seed that is independent from the data may be encrypted to obtain a “cryptographic pad”, which may be XORed with the cache line to obtain the final encryption. For spatial uniqueness, the address of the cache line may be used as a component of the seed and for temporal uniqueness, a per-line counter may be associated with each cache line, wherein the counter may be incremented on each write to the cache line in question.
To reduce space overhead associated with storing the counter values, a counter tree structure may be used, wherein only top level root counters are stored on-chip in SRAM (static random access memory). In such a solution, each node in the counter tree may correspond to a cache line that holds multiple counters and carries a message authentication code (MAC) that is embedded in the cache line (e.g., “eMAC”). An eMAC at a given level in the counter tree may be generated from a corresponding counter value at the next highest level in the tree. Thus, as read and/or write requests are received, a “tree walk” may be conducted in which tree nodes are loaded into a centralized internal cache for verification of the request. During the tree walk, a centralized tracker may be used to monitor dependencies between pending requests. The centralized tracker may lack scalability because different types of platforms may use varying numbers of tree levels to cover different protected memory sizes. Moreover, requests that conflict at any level of the tree may be suspended upon receipt even though the requests may potentially be completed before the conflicting nodes are reached during the tree walk.